import java.util.Stack;

public class Sort {

    /**
     * 插入排序
     * 时间复杂度 O(N^2)
     * 适应性强，适用于待排序序列基本有序
     * 空间复杂度 O(1)
     * 稳定
     * */
    public static void InsertionSort(int[] arr) {
        int i = 0;
        int sz = arr.length;
        while (i<sz-1) {
            int j = i+1;
            int tmp = arr[j];
            while (j-1>=0){
                if(arr[j-1]>=tmp){
                    arr[j] = arr[j-1];
                    j--;
                }else
                    break;
            }
            arr[j]=tmp;
            i++;
        }
    }
    public static void InsertionSort(int[] arr,int begin,int end) {
        for (int i = begin; i < end; i++) {
            int j = i+1;
            int tmp = arr[j];
            while (j-1>=begin){
                if(arr[j-1]>=tmp){
                    arr[j] = arr[j-1];
                    j--;
                }else
                    break;
            }
            arr[j]=tmp;
        }
    }

    /**
     * 希尔排序
     * */
    public static void ShellSort(int[] arr) {
        int gap = arr.length;
        int sz = arr.length;
        while (gap>1)
        {
            gap=gap/3+1;
            int i = 0;
            while (i<gap){
                for (int j = i+gap; j < sz; j+=gap) {
                    int tmp = arr[j];
                    int zi = j;
                    while(zi-gap>=0){
                        if(arr[zi-gap]>tmp){
                            arr[zi] = arr[zi-gap];
                            zi-=gap;
                        }else
                            break;
                    }
                    arr[zi]=tmp;
                }
                i++;
            }
        }
    }

    /**
     * 选择排序
     * */
    public static void selectSort(int[] arr){
        int sz = arr.length;
        for (int i = 0; i < sz-1; i++) {
            int mi = i;
            int min = arr[i];
            int y = mi+1;
            for (; y < sz; y++) {
                if(arr[y]<min){
                    mi = y;
                    min = arr[mi];
                }
            }
            int tmp = arr[mi];
            arr[mi] = arr[i];
            arr[i] = tmp;
        }
    }

    /**
     * 双向选择排序
     * */
    public static void doubleSelectSort(int[] arr){
        int left = 0;
        int right = arr.length-1;
        int sz = arr.length;
        while(left<right){
            int maxi = left;
            int mini = left;
            int max = arr[maxi];
            int min = arr[mini];
            for (int i = left+1; i <= right; i++) {
                if(arr[i]<min){
                    min = arr[i];
                    mini = i;
                }else if(arr[i]>max){
                    max = arr[i];
                    maxi = i;
                }
            }
            int tmp = arr[mini];
            arr[mini] = arr[left];
            arr[left] = tmp;
            if(left==maxi){
                maxi=mini;
            }
            tmp = arr[maxi];
            arr[maxi] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 堆排序
     * */
    private static void xiangXiaTiaoZhen(int[] arr,int pr,int sz)
    {
        int ch = 2*pr+1;
        while (ch<sz) {
            if(ch+1<sz&&arr[ch+1]>arr[ch])
                ch++;
            if(arr[ch]>arr[pr]){
                int tmp = arr[ch];
                arr[ch]=arr[pr];
                arr[pr]=tmp;
            }else
                return;
            pr = ch;
            ch = 2*pr+1;
        }
    }
    private static void jianDaDui(int[] arr) {
        int sz = arr.length;
        int i =(sz-2)/2;
        for (; i >=0 ; i--) {
            xiangXiaTiaoZhen(arr,i,sz);
        }
    }
    private static void del(int[] arr,int sz)
    {
        int tmp = arr[0];
        arr[0]=arr[sz-1];
        arr[sz-1]=tmp;
        xiangXiaTiaoZhen(arr,0,sz-1);
    }
    public static void heapSort(int[] arr){
        jianDaDui(arr);
        int sz = arr.length;
        for (int i = 0; i < sz-1; i++) {
            del(arr,sz-i);
        }
    }

    /**
     * 选择排序
     * */
    public static void bubbleSort(int[] arr){
        int sz = arr.length;
        for (int i = 0; i < sz-1; i++) {
            boolean flag = true;
            for (int j = 0; j < sz-1-i; j++) {
                if(arr[j+1]<arr[j]){
                    int tmp = arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=tmp;
                    flag=false;
                }
            }
            if(flag)
                break;
        }
    }

    /**
     * 快速排序
     * */
    public static void quickSort(int[] arr){
        quickHoare(arr,0,arr.length-1);
    }
    //hoare版本
    public static void quickHoare(int[] arr,int begin,int end){
        if(begin>=end)
            return;
        if(begin-end+1<=16){
            InsertionSort(arr,begin,end);
            return;
        }
        int min = middleNum(arr,begin,end);
        int a = arr[begin];
        arr[begin] = arr[min];
        arr[min]= a;
        int tmp = arr[begin];
        int left = begin;
        int right = end;
        while (right>left){
            while (right>left&&arr[right]>=tmp){
                right--;
            }
            while (right>left&&arr[left]<=tmp){
                left++;
            }
            if(right>left){
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }else
                break;
        }
        int t = arr[left];
        arr[left] = arr[begin];
        arr[begin] = t;
        quickHoare(arr,begin,left-1);
        quickHoare(arr,left+1,end);
    }
    //挖坑法
    public static void quickHole(int[] arr,int begin,int end){
        if(begin>=end)
            return;
        if(begin-end+1<=16){
            InsertionSort(arr,begin,end);
            return;
        }
        int min = middleNum(arr,begin,end);
        int a = arr[begin];
        arr[begin] = arr[min];
        arr[min]= a;
        int tmp = arr[begin];
        int hole = begin;
        int left = begin;
        int right = end;
        while (right>left){
            while (right>left&&arr[right]>=tmp){
                right--;
            }
            if(right>left){
                arr[hole] = arr[right];
                hole = right;
            }
            while (right>left&&arr[left]<=tmp){
                left++;
            }
            if(right>left){
                arr[hole] = arr[left];
                hole = left;
            }
        }
        arr[hole] = arr[left];
        arr[left] = tmp;
        quickHole(arr,begin,left-1);
        quickHole(arr,left+1,end);
    }
    //前后指针法
    public static void quickP(int[] arr,int begin,int end){
        if(begin>=end)
            return;
        if(begin-end+1<=16){
            InsertionSort(arr,begin,end);
            return;
        }
        int min = middleNum(arr,begin,end);
        int a = arr[begin];
        arr[begin] = arr[min];
        arr[min]= a;
        int cu = begin;
        int pr = begin+1;
        int tmp = arr[begin];
        while(pr<=end){
            if(arr[pr]>tmp){
                pr++;
            }else{
                cu++;
                int t = arr[cu];
                arr[cu] = arr[pr];
                arr[pr] = t;
                pr++;
            }
        }
        int t = arr[cu];
        arr[cu] = arr[begin];
        arr[begin] = t;
        quickP(arr,begin,cu-1);
        quickP(arr,cu+1,end);
    }
    //优化：三数取中
    private static int middleNum(int[] arr,int left,int right){
        int min = (left+right)/2;
        if(arr[left]>arr[right]){
            if(arr[min]<arr[right])
                return right;
            else if(arr[min]>arr[left])
                return left;
            else
                return min;
        } else{
            if(arr[min]>arr[right])
                return right;
            else if(arr[min]<arr[left])
                return left;
            else
                return min;
        }
    }
    //非递归
    public static void quickSortNot(int[] arr){
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length-1);
        while (!stack.isEmpty()){
            int end = stack.pop();
            int begin = stack.pop();
            int tmp = arr[begin];
            int left = begin;
            int right = end;
            while (right>left){
                while (right>left&&arr[right]>=tmp){
                    right--;
                }
                while (right>left&&arr[left]<=tmp){
                    left++;
                }
                if(right>left){
                    int t = arr[left];
                    arr[left] = arr[right];
                    arr[right] = t;
                }else
                    break;
            }
            int t = arr[left];
            arr[left] = arr[begin];
            arr[begin] = t;
            if(left+1<end){
                stack.push(left+1);
                stack.push(end);
            }
            if(left-1>begin){
                stack.push(begin);
                stack.push(left-1);
            }
        }
    }

    /**
     * 归并排序
     * */
    public static void mergeSort(int[] arr){
        int[] a = new int[arr.length];
        merge(arr,0, arr.length-1, a);
    }
    private static void merge(int[] arr,int begin,int end,int[] a){
        if(begin>=end)
            return;
        int min = (begin+end)/2;
        merge(arr,begin,min,a);
        merge(arr,min+1,end,a);
        int i = begin;
        int y = min+1;
        int z = begin;
        while(i<=min&&y<=end){
            if(arr[i]<arr[y]){
                a[z++]=arr[i++];
            } else{
              a[z++]=arr[y++];
            }
        }
        while (i<=min){
            a[z++]=arr[i++];
        }
        while(y<=end){
            a[z++]=arr[y++];
        }
        for (i = begin; i <= end; i++) {
            arr[i]=a[i];
        }
    }
    //非递归实现
    public static void mergeSortNor(int[] arr){
        int[] a = new int[arr.length];
        int gap = 1;
        while (gap< arr.length){
            for (int y = 0; y < arr.length; y+=gap*2) {
                int begin1 = y;
                int end1 = begin1+gap-1;
                int begin2 = begin1+gap;
                int end2 = begin2+gap-1;
                if(end1>= arr.length||begin2>= arr.length)
                    break;
                if(end2>=arr.length) {
                    end2= arr.length-1;
                }
                int z = begin1;
                while(begin1<=end1&&begin2<=end2){
                    if(arr[begin1]<arr[begin2]){
                        a[z++]=arr[begin1++];
                    } else{
                        a[z++]=arr[begin2++];
                    }
                }
                while (begin1<=end1){
                    a[z++]=arr[begin1++];
                }
                while(begin2<=end2){
                    a[z++]=arr[begin2++];
                }
                for (int i = y; i <= end2; i++) {
                    arr[i]=a[i];
                }
            }
            gap*=2;
        }
    }

    //计数排序
    public static void countSort(int[] arr){
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<min)
                min=arr[i];
            else if(arr[i]>max)
                max = arr[i];
        }
        int[] a = new int[max-min+1];
        for (int i = 0; i < arr.length; i++) {
            a[arr[i]-min]++;
        }
        int y = 0;
        for (int i = 0; i < a.length; i++) {
            int sz = a[i];
            while(sz--!=0){
                arr[y++]=i+min;
            }
        }
    }
}
